package com.xieyong.leetcode;

import java.util.Comparator;
import java.util.PriorityQueue;

public class Leetcode2163 {
    public static void main(String[] args) {
        Leetcode2163 leetcode2163 = new Leetcode2163();
        int[] nums = {47,26,21,40,3,20,12,19,1,11,37,49,50,29,23,32,27,10,49,24,44,43,46,27,2,3,41,35,10,49,38,44,6,27,27,43,5,36,37,16,5,30,12,15,6,50,44,40,17,45,24,33,32,4,35,37,15,17,13,21};
        long l = leetcode2163.minimumDifference(nums);
        System.out.println(l);
    }

    public long minimumDifference(int[] nums) {
        int len = nums.length;
        int n = len / 3;
        PriorityQueue<Long> firstpq = new PriorityQueue<>(new Comparator<Long>() {
            @Override
            public int compare(Long o1, Long o2) {
                return o2.compareTo(o1);
            }
        });
        PriorityQueue<Long> secondpq = new PriorityQueue<>();
        long firstSum = 0;
        long secondSum = 0;
        for (int i = 0; i < n; i++) {
            firstpq.offer((long) nums[i]);
            firstSum += nums[i];
            secondpq.offer((long)nums[len - 1 - i]);
            secondSum += nums[len - 1 - i];
        }
        long res = Long.MAX_VALUE;
        long[][] forlist = new long[3][n + 1];
        forlist[0][0] = firstSum;
        forlist[1][n] = secondSum;
        for (int i = 0; i < n; i++) {
            long firstItem = nums[n + i];
            long firstPeek = firstpq.peek();
            if (firstItem < firstPeek) {
                firstpq.poll();
                firstpq.offer(firstItem);
                firstSum = firstSum + firstItem - firstPeek;
            }
            forlist[0][i + 1] = firstSum;
            long secondItem = nums[2 * n - 1 - i];
            long secondPeek = secondpq.peek();
            if (secondItem > secondPeek) {
                secondpq.poll();
                secondpq.offer(secondItem);
                secondSum = secondSum + secondItem - secondPeek;
            }
            forlist[1][n - 1 - i] = secondSum;
        }
        for (int i = 0; i < forlist[0].length; i++) {
            res = Math.min(res, forlist[0][i] - forlist[1][i]);
        }
//        for (long[] ints : forlist) {
//            for (long anInt : ints) {
//                System.out.print(anInt + "   ");
//            }
//            System.out.println();
//        }
        return res;
    }

}
